package com.hardy.data_structure;

/**
 * Author: Hardy
 * Date:   2019/3/21
 * Description:
 * - 实现数组的插入、删除
 **/
public class Array {

    // 插入元素的数量
    private int length;

    // 扩容锁绒指数
    private int coefficient;

    // 容量
    private int capacity;

    // 数组
    private int[] arr;

    public Array() {
        this(5);
    }

    public Array(int capacity) {
        this.length = 0;
        this.coefficient = 2;
        this.capacity = capacity;
        this.arr = new int[capacity];
    }

    // 追加元素
    public void add(int elem) {
        // 扩容检查
        if (length == capacity) {
            expand();
        }
        arr[length++] = elem;
    }

    // 插入(可以尾部插入)
    public void insert(int idx, int elem) {
        if (idx < 0 || idx > length)
            System.out.println("位置不合法");

        if (length == capacity) {
            expand();
        }

        for (int i = length - 1; i >= idx; i--) {
            arr[i + 1] = arr[i];
        }

        length++;
        arr[idx] = elem;
    }

    // 删除元素
    public void del(int elem) {
        int idx = find(elem);
        if (idx == -1) return;

        remove(idx);
    }

    // 删除索引位置
    public void remove(int idx) {
        if (idx < 0 || idx >= length)
            System.out.println("位置不合法");

        for (int i = idx; i < length; i++) {
            arr[i] = arr[i + 1];
        }

        length--;
        // 缩容
        if (length * coefficient < capacity) {
            shrink();
        }
    }

    // 查找元素
    public int find(int elem) {
        for (int i = 0; i < length; i++) {
            if (arr[i] == elem) return i;
        }
        return -1;
    }

    public void print() {
        System.out.println("长度: " + length + "\n容量:" + capacity);

        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < length - 1; i++) {
            sb.append(arr[i]).append(",");
        }
        if (length > 0) sb.append(arr[length - 1]);
        sb.append("]");
        System.out.println("内容: " + sb.toString());
        System.out.println("---------------------------------------");
    }

    private void expand() {
        int[] temp = new int[capacity * coefficient];

        copy(arr, temp, length);

        arr = temp;
        capacity = arr.length;
    }

    private void shrink() {
        int[] temp = new int[capacity / coefficient];

        copy(arr, temp, length);

        this.arr = temp;
        this.capacity = arr.length;
    }

    private void copy(int[] orig, int[] dist, int length) {
        // System.arraycopy(arr, 0, temp, 0, capacity); Jdk数组拷贝
        for (int i = 0; i < length; i++) {
            dist[i] = orig[i];
        }
    }
}
